package uestc.lj.basic.greedy;

import java.util.PriorityQueue;

/**
 * 哈夫曼树解决切金条代价问题
 *
 * @Author:Crazlee
 * @Date:2021/11/24
 */
public class Code03_LessMoneySplitGold {
	public static int lessMoney(int[] arr) {
		PriorityQueue<Integer> queue = new PriorityQueue<>();
		for (int i = 0; i < arr.length; i++) {
			queue.add(arr[i]);
		}
		int sum = 0;
		int cur = 0;
		while (queue.size() > 1) {
			cur = queue.poll() + queue.poll();
			sum += cur;
			queue.add(cur);
		}
		return sum;
	}
}
